UVa/11448 - Who said crisis/bigint-2007.07.07/BigIntegerUtils.hh

   1 /*
   2 * Matt McCutchen's Big Integer Library
   3 */
   4
   5 #ifndef BIGINTEGERUTILS
   6 #define BIGINTEGERUTILS
   7
   8 #include "BigInteger.hh"
   9 #include <string>
  10 #include <iostream>
  11
  12 /*
  13 * This file includes:
  14 * (1) `std::string <=> BigUnsigned/BigInteger' conversion routines easier than `BigUnsignedInABase'
  15 * (2) << and >> operators for BigUnsigned/BigInteger, std::istream/std::ostream
  16 */
  17
  18 // Conversion routines.  Base 10 only.
  19 std::string easyBUtoString(const BigUnsigned &x);
  20 std::string easyBItoString(const BigInteger &x);
  21 BigUnsigned easyStringToBU(const std::string &s);
  22 BigInteger easyStringToBI(const std::string &s);
  23
  24 // Creates a BigInteger from data such as `char's; read below for details.
  25 template <class T>
  26 BigInteger easyDataToBI(const T* data, BigInteger::Index length, BigInteger::Sign sign);
  27
  28 // Outputs x to os, obeying the flags `dec', `hex', `bin', and `showbase'.
  29 std::ostream &operator <<(std::ostream &os, const BigUnsigned &x);
  30
  31 // Outputs x to os, obeying the flags `dec', `hex', `bin', and `showbase'.
  32 // My somewhat arbitrary policy: a negative sign comes before a base indicator (like -0xFF).
  33 std::ostream &operator <<(std::ostream &os, const BigInteger &x);
  34
  35 /*
  36 * =================================
  37 * BELOW THIS POINT are template definitions; above are declarations.  See `NumberlikeArray.hh'.
  38 */
  39
  40 /*
  41 * Converts binary data to a BigInteger.
  42 * Pass an array `data', its length, and the desired sign.
  43 *
  44 * Elements of `data' may be of any type `T' that has the following
  45 * two properties (this includes almost all integral types):
  46 *
  47 * (1) `sizeof(T)' correctly gives the amount of binary data in one
  48 * value of `T' and is a factor of `sizeof(Blk)'.
  49 *
  50 * (2) When a value of `T' is casted to a `Blk', the low bytes of
  51 * the result contain the desired binary data.
  52 */
  53 template <class T>
  54 BigInteger easyDataToBI(const T* data, BigInteger::Index length, BigInteger::Sign sign) {
  55         // really ceiling(numBytes / sizeof(BigInteger::Blk))
  56         unsigned int pieceSizeInBits = 8 * sizeof(T);
  57         unsigned int piecesPerBlock = sizeof(BigInteger::Blk) / sizeof(T);
  58         unsigned int numBlocks = (length + piecesPerBlock - 1) / piecesPerBlock;
  59
  60         // Allocate our block array
  61         BigInteger::Blk *blocks = new BigInteger::Blk[numBlocks];
  62
  63         BigInteger::Index blockNum, pieceNum, pieceNumHere;
  64
  65         // Convert
  66         for (blockNum = 0, pieceNum = 0; blockNum < numBlocks; blockNum++) {
  67                 BigInteger::Blk curBlock = 0;
  68                 for (pieceNumHere = 0; pieceNumHere < piecesPerBlock && pieceNum < length;
  69                         pieceNumHere++, pieceNum++)
  70                         curBlock |= (BigInteger::Blk(data[pieceNum]) << (pieceSizeInBits * pieceNumHere));
  71                 blocks[blockNum] = curBlock;
  72         }
  73
  74         // Create the BigInteger.
  75         BigInteger x(blocks, numBlocks, sign);
  76
  77         delete blocks;
  78         return x;
  79 }
  80
  81 #endif